package cn.itcast.zt.leetcode.other;

import cn.itcast.zt.leetcode.element.TreeNode;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class Other_Algorithm {
    /**
     * 70. 爬楼梯
     * 需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     */
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1 ;

        for (int i = 1; i <= n; i++) {
            p = q ;
            q = r ;
            r = p + q ;
        }

        return r ;
    }

    /**
     * 112. 路径总和
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

   /* public static void main(String[] args) {
        int[] numbers = {1, 3, 2, 1, 3, 2, 1, 3, 2};
        sortArray(numbers);
        System.out.println(Arrays.toString(numbers));

        System.out.println(func(2, 4));
    }*/

    /**
     * 一个整数数组,只有1、2、3三种数字,要求对数组降序排序,使得3在前面,2在中间
     */
    public static void sortArray(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }

        int left = 0; // 指向数组的开始
        int mid = 0;  // 用于遍历数组的指针
        int right = array.length - 1; // 指向数组的结束

        while (mid <= right) {
            // 根据当前元素的值，调整指针位置
            switch (array[mid]) {
                case 1:
                    // 交换left和mid指向的元素，并将left向右移动
                    swap(array, left++, mid++);
                    break;
                case 2:
                    // 仅将mid向右移动
                    mid++;
                    break;
                case 3:
                    // 交换mid和right指向的元素，同时将right向左移动，mid也向右移动
                    swap(array, mid, right--);
                    break;
            }
        }
    }

    // 交换数组中的两个元素
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 题目1：
     * 共n级台阶，可走m步，每次步数可走1个台阶，可上台阶、可下台阶，但不能越界（小于0或者大于n）
     * 问：从0级台阶出发，共有多少种路径，可以走完m步，到最后一级第n级台阶
     * 3级台阶，3步，共有1种解法
     * 2级台阶，4步，共有2种解法
     *
     * 0->1->2->1->2
     * 0->1->0->1->2
     */
    /**
     * 递归函数计算到达n级台阶的路径数，m为剩余步数
     */
    public static Integer func(Integer n, Integer m) {
        // 递归终止条件：如果剩余步数为0且当前台阶数为0，返回1
        if (m == 0 && n == 0){
            return 1 ;
        }

        // 如果剩余步数为0且未到达台阶顶部，或者剩余步数小于0，返回0
        if (m == 0 || m < 0) {
            return 0 ;
        }

        /**
         * 如果台阶数小于0，返回0
         */
        if (n <= 0) {
            return 0 ;
        }

        // 递归：当前位置的路径数是上一步台阶的路径数加上当前台阶的路径数（可以上一步、可以下一步）
        return func(n - 1, m - 1) + func(n + 1, m - 1) ;
    }

    /*public static void main(String[] args) {
        Test test = new Test() ;
        Thread threadA = new Thread(() -> {
            while(true) {
                test.printA();
            }
        }) ;

        Thread threadB = new Thread(() -> {
            while(true) {
                test.printB();
            }
        }) ;

        Thread threadC = new Thread(() -> {
            while(true) {
                test.printC();
            }
        }) ;

        threadA.start();
        threadB.start();
        threadC.start();
    }

    private int flag = 1 ;
    // 打印A
    public synchronized void printA() {
        while(flag != 1) {
            try {
                wait();
            }catch (Exception e) {
                e.printStackTrace();
            }
        }

        System.out.println("a");
        flag = 2;
        notifyAll();
    }

    // 打印B
    public synchronized void printB() {
        while(flag != 2) {
            try {
                wait();
            }catch (Exception e) {
                e.printStackTrace();
            }
        }

        System.out.println("b");
        flag = 3;
        notifyAll();
    }

    // 打印C
    public synchronized void printC() {
        while(flag != 3) {
            try {
                wait();
            }catch (Exception e) {
                e.printStackTrace();
            }
        }

        System.out.println("c");
        flag = 1;
        notifyAll();
    }*/

    /*public static void main(String[] args) {
        Test test = new Test() ;

        Thread threadA = new Thread(() -> {
                while(true) {
                    try {
                        test.printA();
                    }catch (InterruptedException ex) {
                        ex.printStackTrace();
                    }
                }
        }) ;

        Thread threadB = new Thread(() -> {
            while(true) {
                try {
                    test.printB();
                }catch (InterruptedException ex) {
                    ex.printStackTrace();
                }
            }
        }) ;

        Thread threadC = new Thread(() -> {
            while(true) {
                try {
                    test.printC();
                }catch (InterruptedException ex) {
                    ex.printStackTrace();
                }
            }
        }) ;

        threadA.start();
        threadB.start();
        threadC.start();
    }

    private final Object lock = new Object() ;
    private int current = 1 ;

    // 打印A
    public void printA() throws InterruptedException {
        while(true) {
            synchronized (lock) {
                if (current == 1) {
                    System.out.println("a");
                    current = 2 ;
                    lock.notify();
                    break;
                }

                lock.wait();
            }
        }
    }

    // 打印B
    public void printB() throws InterruptedException {
        while(true) {
            synchronized (lock) {
                if (current == 2) {
                    System.out.println("b");
                    current = 3 ;
                    lock.notify();
                    break;
                }

                lock.wait();
            }
        }
    }

    // 打印C
    public void printC() throws InterruptedException {
        while(true) {
            synchronized (lock) {
                if (current == 3) {
                    System.out.println("c");
                    current = 1 ;
                    lock.notify();
                    break;
                }

                lock.wait();
            }
        }
    }*/

    public static void main(String[] args) throws Exception {
        Other_Algorithm test = new Other_Algorithm() ;

        Thread threadA = new Thread(() -> {
            while(true) {
                test.printA();
            }
        }) ;

        Thread threadB = new Thread(() -> {
            while(true) {
                test.printB();
            }
        }) ;

        Thread threadC = new Thread(() -> {
            while(true) {
                test.printC();
            }
        }) ;

        threadA.start();
        threadB.start();
        threadC.start();
    }

    private final ReentrantLock lock = new ReentrantLock() ;
    private final Condition conditionA = lock.newCondition() ;
    private final Condition conditionB = lock.newCondition() ;
    private final Condition conditionC = lock.newCondition() ;
    private int flag = 1 ;

    // 打印A
    public void printA() {
        lock.lock();
        try {
            while(flag != 1) {
                conditionA.await();
            }
            System.out.println("a");
            flag = 2 ;
            conditionB.signal();
        }catch (Exception ex) {
            ex.printStackTrace();
        }finally {
            lock.unlock();
        }
    }
    // 打印B
    public void printB() {
        lock.lock();
        try {
            while(flag != 2) {
                conditionB.await();
            }
            System.out.println("b");
            flag = 3 ;
            conditionC.signal();
        }catch (Exception ex) {
            ex.printStackTrace();
        }finally {
            lock.unlock();
        }
    }

    // 打印C
    public void printC() {
        lock.lock();
        try {
            while(flag != 3) {
                conditionC.await();
            }
            System.out.println("c");
            flag = 1 ;
            conditionA.signal();
        }catch (Exception ex) {
            ex.printStackTrace();
        }finally {
            lock.unlock();
        }
    }

    /**
     * 将一个二叉搜索树转化为双链表
     */
    TreeNode head = null ;
    TreeNode tail = null ;
    // 中序遍历构建双链表
    public void covertInOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        covertInOrder(root.left);
        if (tail == null) {
            head = root ;
            tail = root ;
        }else {
            root.prev = tail ;
            tail.right = root ;
            tail = root ;
        }
        covertInOrder(root.right);
    }

    public TreeNode getHead() {
        return head ;
    }
}
